package lc.q1_50;

public class Q41 {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0;i < nums.length;) {
            // 将数组移位，对于num<=0或者num>nums.length，不处理
            int num = nums[i];
            if(num <= 0 || num > nums.length || num == nums[num-1]  ) {
                i ++;
                continue;
            }
            nums[i] = nums[num-1];
            nums[num-1] = num;
        }
        for (int i = 0;i < nums.length;i ++) {
            if (nums[i] != (i + 1)) {
                return i + 1;
            }
        }
        return nums.length+1;
    }
}
